#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> PII; // distance node
class Dijkstra {
public:
    Dijkstra(int _n) {
        n = _n;
        adj.resize(_n + 1);
        dist.resize(_n + 1, INT_MAX);
    }
    // // 有向边
    void addEdge(int u, int v, int weight) {
        adj[u].push_back({v, weight}); // 这里的是node distance
        adj[v].push_back({u, weight});
    }
    // 无向边
    // void addEdge(int u, int v, int weight) {
    //     adj[u].push_back({v, weight});
    // }
    void running(int start) { // 实际的内部实现
        dist[start] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆，用来更新边
        heap.push({0, start});
        while(!heap.empty()) {
            int u = heap.top().second;
            int weight = heap.top().first;
            heap.pop();
            if(weight > dist[u]) continue; // 表示当前节点不是最新的，当前节点已经不是当前的最短路径了，不需要了
            for(auto& e : adj[u]) {
                int v = e.first;
                int w = e.second;
                if(dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    heap.push({dist[v], v});
                }
            }
        }
    }
    void print() {
        for(int i = 1; i <= n; i++) {
            if(dist[i] == INT_MAX) {
                cout << "Node : " << i << "不可抵达" << endl;
            }else {
                cout << "Node : " << i << " : " << dist[i] << endl;
            }
        }
    }
private:
    int n;
    vector<vector<PII>> adj;
    vector<int> dist;
};
int main() {
    int n, m;
    cout << "Enter number of nodes and edges: ";
    cin >> n >> m;
    Dijkstra dijkstra(n);

    cout << "Enter the edges (u, v, weight): " << endl;
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        dijkstra.addEdge(u, v, weight);
    }

    int start;
    cout << "Enter the starting node: ";
    cin >> start;

    dijkstra.running(start);
    dijkstra.print();

    return 0;
}


